Tree alignment

In computational phylogenetics, tree alignment is the problem of producing a multiple sequence alignment on a set of sequences over a fixed tree.

Formally, tree alignment is the following optimization problem.

Input: A set $S$ of sequences, a phylogenetic tree $T$ leaf-labeled by $S$ and an edit distance function $d$ between sequences,

Output: A labeling of the internal vertices of $T$ such that $\Sigma_{e \in T} d(e)$ is minimized, where $d(e)$ is the edit distance between the endpoints of $e$ .

The task is NP-hard^[1]

References

^ Elias, Isaac (2006), "Settling the intractability of multiple alignment", J Comput Biol 13 (7): 1323–1339, doi:10.1089/cmb.2006.13.1323, PMID 17037961

Tree alignment

See also

References